package it.storm.solution;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class Solutions_42 {
    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};  // output: 6
        int result = trap(height);

        System.out.println(result);
    }

    /**
     * 解法一：线性扫描（1ms）
     * 1. 总共能够接到的雨水数量 = 每个柱子上能够接到的雨水数量的和
     * 2. 每个柱子能够接到的雨水数量由 两侧最高柱子中较低的一侧决定。
     *      2.1 第一根柱子没有左侧的柱子，不计算
     *      2.2 最后一根柱子没有右侧的柱子，不计算
     *      2.3 如果当前柱子的左侧与右侧的最高柱子高度都大于当前柱子的高度，那么能够接到的雨水数量为
     *          两侧最高柱子中较低的一侧 - 当前柱子的高度
     */
    public static int trap(int[] height) {
        int res = 0;
        if (height == null || height.length < 3) {
            // 柱子数量不够 3 根时，一定接不到雨水
            return res;
        }
        int len = height.length;

        // maxRight[3] = 3,索引 3 右侧最高高度为 3
        int[] rightMax = new int[len];
        // 最后一根柱子的高度，默认为右侧最大度
        int max = height[len - 1];
        for (int i = height.length - 2; i > 0; i--) {
            // 当前柱子的右侧最高值
            rightMax[i] = max;
            // 比较并更新右侧最大值
            max = Math.max(max, height[i]);
        }

        // 第一根柱子的高度，默认为左侧最大度
        int leftMax = height[0];
        for (int i = 1; i < height.length - 1; i++) {
            if (leftMax > height[i] && rightMax[i] > height[i]) {
                // 左右两侧柱子的高度都大于当前柱子时，计算接雨水的数量
                res += Math.min(leftMax, rightMax[i]) - height[i];
            }
            // 比较并更新左侧最大值
            leftMax = Math.max(leftMax, height[i]);
        }
        return res;
    }

    /**
     * 解法二：单调栈（3ms）
     * 单调递减栈，栈中存放的是索引
     * 当前元素大于栈顶元素时，那么计算栈顶元素所在位置的接水量
     * 通过左侧和右侧的高度，即计算出接水量
     */
    public static int trap2(int[] height) {
        if (height == null || height.length < 3) {
            // 柱子数量不够 3 根时，一定接不到雨水
            return 0;
        }
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                // 计算出 prev 索引处，能够接到的雨水数量
                int prev = stack.pop();
                int prevH = height[prev];
                // 从栈中找到左侧中比 prev 高的柱子，即其前一元素
                while (!stack.isEmpty() && height[stack.peek()] == prevH) {
                    // 可能存在连续的并且相同高度的柱子
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    // 宽度
                    int weight = i - stack.peek() - 1;
                    // 高度（两侧中高度较低的一侧，减去 prev 索引处本身的高度，即是接到的雨水的高度）
                    int h = Math.min(height[stack.peek()], height[i]) - prevH;
                    // 索引 prev 处，能够接到的雨水
                    res += weight * h;
                }
            }
            stack.push(i);
        }
        return res;
    }
}
